package com.example.sequence.selfLinkedList;

import java.util.Arrays;

/*
线性顺序表
 */
public class SequenceList<T> {
    private final int DEFAULT_SIZE=8;//数组默认长度
    private int capacity;      //数组长度
    private int size=0;        //当前数组中元素个数
    private Object[] elementData;  //线性表实现的底层数组

    //默认初始化数组
    public SequenceList() {
        capacity=DEFAULT_SIZE;
        elementData=new Object[capacity];
    }

    //当数组已经满了后扩大容量
    private void boardCapacity(int ruleCapacity){
        if(capacity<ruleCapacity){
            //每次将数组容量按照原来扩大两倍，直到容量大于指定容量
            while(capacity<ruleCapacity){
                capacity=capacity*2;
            }
            elementData= Arrays.copyOf(elementData, capacity);
        }
    }

    //获得线性表大小
    public int getLength(){
        return size;
    }

    //重写toString方法
    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<size;i++)
        {
            sb=sb.append(elementData[i]+" ");
        }
        return sb+"";
    }

    //按照顺序添加元素
    public void add(T element){
        insert(element,size);
    }

    public void insert(T element,int index){
        if(index<0||index>size)
        {
            throw new IndexOutOfBoundsException("索引越界");
        }
        boardCapacity(size+1);
        /*
         * 在elementData中从index开始复制，复制长度size-index,将
         * 复制的元素复制到目标数组elmentData的index+1位上直到后面结束
         * 即将index位置空出，每个元素后移一位
         */
        System.arraycopy(elementData, index, elementData, index+1, size-index);

        elementData[index]=element;
        size++;
    }


    //查找指定元素的位置
    //返回-1即没找到
    public String locate(T element){
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<size;i++)
        {
            if(element.equals(elementData[i]))
            {
                sb=sb.append(i+" ");
            }
        }
        if(sb.length()<=0)
            return "无此元素";
        return sb+"";
    }


    //删除指定位置的元素
    //@param index 元素索引
    public void delete(int index){
        if(index<0||index>size)
        {
            throw new IndexOutOfBoundsException("索引越界");
        }
        int length=size-index-1;
        //删除元素所有元素向前移动
        if(length>0)
            System.arraycopy(elementData, index+1, elementData, index, length);
        //将最后一个数删除
        elementData[--size]=null;
    }

    public boolean isEmpty(){
        if(size>0){
            return false;
        }
        return true;
    }


     //清空线性表数据
    public void clearSequenceList(){
        if(elementData!=null){
            for(int i=0;i<size;i++)
            {
                elementData[i]=null;
            }
            size=0;
        }
    }

    //根据索引得到元素
    public Object get(int index){
        return elementData[index];
    }

    //删除最后一个元素
    public void remove(){
        delete(size-1);
    }
    //遍历线性表
    public void printSequenceList(){
        if(elementData==null){
            System.out.println("当前无数据");
        }else{
            for(int i=0;i<size;i++)
            {
                System.out.print(elementData[i]+" ");
            }
        }
    }
}
